package com.cat.graphTheory;

import java.util.Arrays;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/maximum-number-of-events-that-can-be-attended/description/
 * @create 2025/10/7 20:50
 * @since JDK17
 */

public class Solution38 {
    public int maxEvents(int[][] events) {
        Arrays.sort(events, (a, b) -> a[0] - b[0]);
        int n = events.length, max = Integer.MIN_VALUE, min = events[0][0], ans = 0, i = 0;
        for (var event : events) {
            max = Math.max(max, event[1]);
        }
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int day = min; day <= max; day++) {
            while (i < n && events[i][0] == day) {
                heap.add(events[i++][1]);
            }
            while (!heap.isEmpty() && heap.peek() < day) {
                heap.poll();
            }
            if (!heap.isEmpty()) {
                ans++;
                heap.poll();
            }
        }

        return ans;
    }
}
